package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by hao on 17-3-15.
 */
public class ValidParentheses {
//  public boolean isValid(String s) {
//    char[] pArray = new char[]{
//            '(', ')', '[', ']', '{', '}'
//    };
//    char p = 0;
//    char[] strArray = s.toCharArray();
//    for (int i = 0; i < strArray.length; i++) {
//      for (int j = 0; j < pArray.length; j++) {
//        if (strArray[i] == pArray[j]){
//          if (j % 2 == 0){
//            p = pArray[j-1];
//          }else {
//            p = pArray[j+1];
//          }
//        }
//      }
//      Node node = new Node(strArray[i]);
//      for (int j = i+1; j < strArray.length; j++) {
//        if (strArray[j] != p){
//          node.right = new Node(strArray[j]);
//        }else {
////          node = null;
//        }
//      }
//
//      for (int j = i; j < s.length(); j++) {
//
//      }
//
//
//
//    }
//    return true;
//  }

    public static void main(String[] args) {
        ValidParentheses validParentheses = new ValidParentheses();
        boolean result = validParentheses.isValid("()([])()");
        System.out.println(result);
    }

    /**
     * 思路：
     * 1. 把目标字符串里的字符往数组里放，匹配一定发生在数组的末位字符与目标字符之间
     * 2. 外层遍历目标串，内层遍历模式串
     * 3. 内层遍历主要是判断是否将目标字符放入目标数组，也就是说判断是否移除目标数组末位字符(匹配时)
     * 4. 内层遍历时，只有目标字符为结束型符号时才有可能匹配，否则直接添加进目标数组(步长为2的遍历优化)
     * 5. 判断最终目标数组是否含有元素
     * <p>
     * 优化思路： char数组
     *
     * @param s the original String
     * @return
     */
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) return false;
        int[] pArray = new int[]{
                '(', ')', '[', ']', '{', '}'
        };
        char[] strArray = s.toCharArray();
        List<Integer> list = new ArrayList<>();

        for (int aStrArray : strArray) {
            boolean match = false;
            for (int i = 0; i < pArray.length; i += 2) {
                if (list.size() >= 1) {
                    int lastChar = list.get(list.size() - 1);
                    if (lastChar == pArray[i + 1]) return false;
                    if (lastChar != pArray[i]) continue;
                    if (aStrArray == pArray[i + 1]) match = true;
                }
            }
            if (match) {
                list.remove(list.size() - 1);
            } else {
                list.add(aStrArray);
            }
        }
        return list.size() == 0;
    }
}
